package P3排序算法;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Random;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[30];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(1000);
        }
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) { //O(N*M)
        int max = arr[0];
        //O(N)
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        ArrayDeque<Integer>[] temp = new ArrayDeque[10];
        for (int i = 0; i < temp.length; i++) {
            temp[i] = new ArrayDeque<>();
        }
        int radix = (max + "").length();
        //O(M)
        for (int r = 1; r <= radix; r++) {
            //分类
            //O(N)
            for (int i = 0; i < arr.length; i++) {
                int index = getIndex(arr[i], r);
                temp[index].addLast(arr[i]);
            }
            //合并
            //O(N)
            int k = 0;
            for (int i = 0; i < temp.length; i++) {
                while (!temp[i].isEmpty()) {
                    arr[k++] = temp[i].removeFirst();
                }
            }
        }
    }

    private static int getIndex(int num, int r) {
        String str = num + "";
        //"12345"
        // 01234
        if (r > str.length()) {
            return 0;
        } else {
            return str.charAt(str.length() - r) - '0';
        }
    }
}